package com.xiaomitest;

import java.util.HashMap;

public class PreArrSum {
    // 前缀和

    public int subarraySum(int[] nums, int k) {
        //前缀和优化
        int count = 0;
        int pre = 0;
        HashMap<Integer, Integer> map = new HashMap();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }
            //这里map.getOrDefault(pre, 0)的作用是如果map函数中有pre这个key，那么就用这个key对应的value值，如果没有就使用默认值0
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

    /**
     * 看到这里我们再来看一道题：给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
     * 示例：
     * 输入：A = [4,5,0,-2,-3,1], K = 5
     * 输出：7
     * 解释：
     * 有 7 个子数组满足其元素之和可被 K = 5 整除：
     * [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
     *
     * 这道题同样可以使用前缀和+hashmap优化的方式去做，首先我们要确定找到满足以下公式的前缀和
     * (preSum[i]−preSum[j]) mod K=0
     * (preSum[i]−preSum[j]) mod K=0
     *
     * 同样的，我们这里再做一个转换：
     * preSum[i] mod K=preSum[j] mod K
     * preSum[i] mod K=preSum[j] mod K
     *
     * 因为我们也并不需要关心究竟是哪一个数组下标满足以上的公式，只需要知道前缀和 preSum[j] % K 满足当前下标的前缀和 preSum[i] % K 的数量。但是这里我们需要注意，因为需要用到求模（会出现负数），所以需要对求模做一些调整。举一个简单的例子
     * preSum[i] = 4, preSum[j] = -3, K = 7;
     * (preSum[i] -preSum[j]) % K = (4-(-3)) % 7 = 0;满足上式；
     * 转换后得到的是：4 % 7 = 4 和 -3 % 7 = -3 ，这两个这样看起来明显不等，但是他们应该是在一组内。
     *
     * 所以我们这里需要做以下调整：
     * (preSum[i] mod K+K)mod K
     * (preSum[i] mod K+K)mod K
     *
     *
     */



    public int subarraysDivByK(int[] A, int K) {
            //前缀和
            int count = 0;
            int len = A.length;
            int preSum = 0;
            HashMap<Integer,Integer> map = new HashMap();
            map.put(0,1);
            for(int i=0;i<len;i++){
                preSum += A[i];
                int temp = (preSum % K + K) % K;
                if(map.containsKey(temp)){
                    count += map.get(temp);
                }
                map.put(temp, map.getOrDefault(temp, 0) + 1);
            }
            return count;

    }


}
